package top150_v2

func isValid(s string) bool {
	var stack []byte
	var idx = 0
	for idx < len(s) {
		if len(stack) == 0 {
			if isRight(s[idx]) {
				return false
			}
			stack = append(stack, s[idx])
		} else {
			if !isRight(s[idx]) {
				stack = append(stack, s[idx])
			} else {
				if pair(stack[len(stack)-1], s[idx]) {
					stack = stack[:len(stack)-1]
				} else {
					return false
				}
			}
		}
		idx++
	}
	return len(stack) == 0
}

func pair(left, right byte) bool {
	if left == '(' && right == ')' {
		return true
	}
	if left == '[' && right == ']' {
		return true
	}
	if left == '{' && right == '}' {
		return true
	}
	return false
}

func isRight(a byte) bool {
	if a == ')' || a == ']' || a == '}' {
		return true
	}
	return false
}

type LRUCache struct {
	Cache       map[int]*Node
	Capacity    int
	Count       int
	VirtualHead *Node
	VirtaulTail *Node
}

type Node struct {
	Val  int
	Key  int
	Pre  *Node
	Next *Node
}

func Constructor(capacity int) LRUCache {
	var res = LRUCache{
		Cache:       make(map[int]*Node),
		VirtualHead: &Node{},
		VirtaulTail: &Node{},
		Capacity:    capacity,
	}
	res.VirtualHead.Next = res.VirtaulTail
	res.VirtaulTail.Pre = res.VirtualHead
	return res
}

func (this *LRUCache) Get(key int) int {
	var cache = this.Cache
	if node, ok := cache[key]; ok {
		this.moveToHead(node)
		return node.Val
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	var cache = this.Cache
	if node, ok := cache[key]; ok {
		node.Val = value
		this.moveToHead(node)
		return
	} else {
		var newNode = &Node{
			Key: key,
			Val: value,
		}
		if this.Count == this.Capacity {
			var tail = this.VirtaulTail.Pre
			var newTail = tail.Pre
			newTail.Next = this.VirtaulTail
			this.VirtaulTail.Pre = newTail
			delete(cache, tail.Key)
		} else {
			this.Count++
		}
		cache[key] = newNode
		this.moveToHead(newNode)
	}
}

func (this *LRUCache) moveToHead(node *Node) {
	var curHead = this.VirtualHead.Next
	if curHead == node {
		return
	}
	if node.Pre != nil {
		node.Pre.Next = node.Next
	}
	if node.Next != nil {
		node.Next.Pre = node.Pre
	}
	this.VirtualHead.Next = node
	node.Pre = this.VirtualHead
	node.Next = curHead
	curHead.Pre = node
}

/**
 * @description:  在排序数组中查找元素的第一个和最后一个位置
 * @keyword:
 * @author: kami
 * @date 2024/4/20 12:13
 */
func searchRange(nums []int, target int) []int {
	var left = 0
	var right = len(nums) - 1
	for left <= right {
		var mid = left + (right-left)/2
		if target > nums[mid] {
			left = mid + 1
		} else if target < nums[mid] {
			right = mid - 1
		} else {
			var leftIdx = findLeft(left, mid, target, nums)
			var rightIdx = findRight(mid, right, target, nums)
			return []int{leftIdx, rightIdx}
		}
	}
	return []int{-1, -1}
}

func findLeft(left, right, target int, nums []int) int {
	for left <= right {
		var mid = left + (right-left)/2
		if nums[mid] < target {
			left = mid + 1
		} else {
			if mid == 0 || nums[mid-1] < target {
				return mid
			}
			right = mid - 1
		}
	}
	return -1
}
func findRight(left, right, target int, nums []int) int {
	for left <= right {
		var mid = left + (right-left)/2
		if nums[mid] > target {
			right = mid - 1
		} else {
			if mid == len(nums)-1 || nums[mid+1] > target {
				return mid
			}
			left = mid + 1
		}
	}
	return -1
}

func addBinary(a string, b string) string {
	var aIdx = len(a) - 1
	var bIdx = len(b) - 1
	var take = uint8(0)
	var res []byte
	for aIdx >= 0 || bIdx >= 0 {
		var curVal uint8
		if aIdx >= 0 && bIdx >= 0 {
			curVal = a[aIdx] - '0' + b[bIdx] - '0' + take
			aIdx--
			bIdx--
		} else if aIdx >= 0 {
			curVal = a[aIdx] - '0' + take
			aIdx--
		} else {
			curVal = b[bIdx] - '0' + take
			bIdx--
		}
		if curVal == 3 {
			curVal = 1
			take = 1
		} else if curVal == 2 {
			curVal = 0
			take = 1
		} else {
			take = 0
		}
		res = append(res, curVal)
	}

	if take == 1 {
		res = append(res, '1')
	}
	var left = 0
	var right = len(res) - 1
	for left < right {
		res[left], res[right] = res[right], res[left]
		left++
		right--
	}
	return string(res)
}

func maximalSquare(matrix [][]byte) int {
	var max = 0
	var dp = make([][]int, len(matrix))
	for i := 0; i < len(matrix); i++ {
		dp[i] = make([]int, len(matrix[i]))
		dp[i][0] = int(matrix[i][0] - '0')
		if dp[i][0] > max {
			max = 1
		}
	}
	for j := 1; j < len(matrix[0]); j++ {
		dp[0][j] = int(matrix[0][j] - '0')
		if dp[0][j] > max {
			max = 1
		}
	}
	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[i]); j++ {
			if matrix[i][j] == '1' {
				dp[i][j] = getMin(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
				if dp[i][j]*dp[i][j] > max {
					max = dp[i][j] * dp[i][j]
				}
			}

		}
	}
	return max
}

func getMin(a, b, c int) int {
	var min = a
	if b < min {
		min = b
	}
	if c < min {
		min = c
	}
	return min
}
